<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>javascript 阶段</title>
</head>
<body>


    <script>

        // 快速排序（递归排序）
        // 基本思想：
            // 1. 找出数组的中间位置（偏）基准
            // 2. 划分三个数组，左边数组，中间数，右边数组
            // 3. 比如。升序的逻辑
            // 递归的方式，把较小的数值存放于左边数组，把较大数值存放于右边数组
            // 重复上述操作，一直到数组的length属性值小于等于1位置
 
        //  递归：
            // 1.函数的自身调用
            // 2.终止调用的条件

         // 定义数组
         var arr = [100,80,20,90,60];
         //  第一次执行函数  基准值 20
         // [].concat([20] , [100,80,90,60])  
         //  第二次执行函数  基准值 80
         // [].concat([20] , [60].concat([80],[100,90]))
         //   第三次执行函数  基准值 90
         // [].concat([20] , [60].concat([80],[].concat([90],[100])))
        //  等待递归函数执行完毕，就是一个排序完成的数组

        //  定义函数 quickSort 
        function quickSort(elements) {
            // 判断数组的length属性是否小于等于1
            if(elements.length <= 1){
                return elements;
            }
            // 找数组中偏中间的索引值（基准值）
            var midIndex = parseInt(elements.length / 2);
            // console.log(midIndex);
            // 找数组中偏中间的索引值的元素
            var middleVal = elements.splice(midIndex,1)[0];
            console.log(middleVal);
            // console.log(elements.splice(midIndex,1)[0]);
            // middleVal = middleVal[0]
            // 定义左边数组
            var left_arr = [];
            // 定义右边的数组
            var right_arr = [];
            // 循环数组 elements 数组
            for(var i = 0 ; i < elements.length ; i ++){
                // 比较数组的元素 
                if(elements[i] < middleVal){
                    // 把较小的元素添加到左边数组
                    left_arr.push(elements[i]);
                }else {
                    // 把较大的元素添加到右边数组
                    right_arr.push(elements[i]);
                }
            }
            // 执行递归
            return quickSort(left_arr).concat([middleVal],quickSort(right_arr))
        }

        //  调用函数 quickSort 
        var res = quickSort(arr);
        console.log(res);// [20, 60, 80, 90, 100]


        // var left = quickSort(left_arr);
        // var right = quickSort(right_arr);
        // return left.concat([middleVal],right);


        var arr1 = [20 , 100 , 40 ,200,  760 , 10];

        function shortsort(elements) {
            if(elements.length <= 1) {
                return elements;
            }
            var too = elements.length;
            var foo = Math.floor(Math.random()*too);
            // var midIndex = parseInt(elements.length/3);
            // console.log(midIndex);
            var middleVal = elements.splice(foo , 1)[0];
            console.log(middleVal);

            var left_arr = [];
            var right_arr = [];
            for(i = 0 ; i < elements.length ; i ++) {
                if(elements[i] < middleVal) {
                    right_arr.push(elements[i]);
                }else {
                    left_arr.push(elements[i]);
                }
            }
            return shortsort(left_arr).concat([middleVal],shortsort(right_arr));
        }
        var res1 = shortsort(arr1);
        console.log(res1);
    </script>
</body>
</html>